#include <stdlib.h>
#include <stdio.h>

// Kruskal算法,生成最小生成树

typedef char VertexType; // 顶点数据类型
typedef int EdgeType;  // 边的权值类型

#define MAXVEX 100       // 最大顶点数
#define MAX 0x7fffffff   // 无穷大

// 图的邻接矩阵表示
typedef struct{
    VertexType vexs[MAXVEX];          // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];     // 邻接矩阵
    int numVertexes, numEdges;        // 图的当前顶点数和边数
} Graph;

// 边的结构体
typedef struct{
    int begin;      // 边的起点
    int end;        // 边的终点
    EdgeType weight; // 边的权值
} Edge;

void createGraph(Graph *G){
    G->numVertexes = 9;
    G->numEdges = 15;
    // 初始化邻接矩阵
    G->vexs[0] = 'A';
    G->vexs[1] = 'B';
    G->vexs[2] = 'C';
    G->vexs[3] = 'D';
    G->vexs[4] = 'E';
    G->vexs[5] = 'F';
    G->vexs[6] = 'G';
    G->vexs[7] = 'H';
    G->vexs[8] = 'I';

    for (int i = 0; i < G->numVertexes; i++){      // 初始化邻接矩阵
        for (int j = 0; j < G->numVertexes; j++){  // 初始化邻接矩阵
            if (i == j){                  
                G->arc[i][j] = 0;  // 对角线为0
            } else {
                G->arc[i][j] = MAX; // 用无穷大表示不连通
            }
        }
    }

    // 建立边(权值)
    // A-B A-F 
    G->arc[0][1] = 10;
    G->arc[0][5] = 11;

    // B-C B-G B-I
    G->arc[1][2] = 18;  
    G->arc[1][6] = 16;
    G->arc[1][8] = 12;

    // C-D C-I
    G->arc[2][3] = 22;
    G->arc[2][8] = 8;

    // D-E D-G D-H D-I
    G->arc[3][4] = 20;
    G->arc[3][6] = 24;
    G->arc[3][7] = 16;
    G->arc[3][8] = 21;

    // E-F E-H
    G->arc[4][5] = 26;
    G->arc[4][7] = 7;

    // F-G
    G->arc[5][6] = 17;

    // G-H
    G->arc[6][7] = 19;

    for (int i = 0; i < G->numVertexes; i++){
        for (int j = 0; j < G->numVertexes; j++){
            G->arc[j][i] = G->arc[i][j]; // 无向图邻接矩阵对称
        }
    }
}

void swap(Edge *edges, int i, int j){
    int temp;
    temp = edges[i].begin;     // 交换边的起点
    edges[i].begin = edges[j].begin;   // 交换边的起点
    edges[j].begin = temp;    // 交换边的起点

    temp = edges[i].end;
    edges[i].end = edges[j].end;   // 交换边的终点
    edges[j].end = temp;

    temp = edges[i].weight;
    edges[i].weight = edges[j].weight;
    edges[j].weight = temp;
}

// 冒泡排序，对边集数组按权值从小到大排序
void sortEdges(Edge *edges, int numEdges){ 
    for (int i = 0; i < numEdges; i++){  // 进行numEdges-1轮排序
        for (int j = i+1; j < numEdges; j++){   // 每轮比较的次数逐渐减少
            if (edges[i].weight > edges[j].weight){   // 交换
                swap(edges, i, j);      
            }
        }
    }
}

// 查找f的终点
int find(int *parent, int f){
    while (parent[f] > 0){ // 寻找f的终点
        f = parent[f];
    }
    return f;
}

// Kruskal算法,生成最小生成树
void Kruskal(Graph G){
    Edge edges[MAXVEX]; // 边集数组
    int k = 0;          // 边集数组的索引

    for (int i = 0; i < G.numVertexes; i++){
        for (int j = i+1; j < G.numVertexes; j++){ // j=i+1避免重复
            if (G.arc[i][j] != MAX){ // 有边
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arc[i][j];
                k++;
            }
        }
    }
    sortEdges(edges, G.numEdges); // 对边集数组按权值从小到大排序

    int parent[MAXVEX]; // 用于保存"已有最小生成树"中每个顶点在树中的终点
    for (int i = 0; i < G.numVertexes; i++){
        parent[i] = 0;  // 初始化"已有最小生成树"中每个顶点在树中的终点为0
    }   
    
    int n,m;  // 记录边的起点和终点
    for (int i = 0; i < G.numEdges; i++){ // 依次选择权值最小的边
        n = find(parent, edges[i].begin); // 取得边的起点的终点
        m = find(parent, edges[i].end);   // 取得边的终点的终点
        if (n != m){    // 如果n和m的终点不同,则将此边加入最小生成树中
            parent[n] = m; // 设置n在树中的终点为m
            printf("(%c, %c) %d\n", G.vexs[edges[i].begin], G.vexs[edges[i].end], edges[i].weight);
        }
    }
}

int main(){
    Graph G;
    createGraph(&G);
    Kruskal(G);
    return 0;
}

